package com.linyaonan.leetcode.sword_to_offer._54;


/**
 * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 4
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 *        5
 *       / \
 *      3   6
 *     / \
 *    2   4
 *   /
 *  1
 * 输出: 4
 *  
 *
 * 限制：
 *
 * 1 ≤ k ≤ 二叉搜索树元素个数
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 常规思路是使用快慢指针来实现，快指针先走k步，慢指针开始与快指针同步走，快指针结束时慢指针指向的就是该内容
     * @param root
     * @param k
     * @return
     */

    int t;
    int count;

    public int kthLargest(TreeNode root, int k) {
        bfs(root, k);
        return t;
    }



    public void bfs(TreeNode r, int k) {
        if (r == null) {
            return;
        } else {
            bfs(r.right, k);
            System.out.println(r.val);
            System.out.println("count:" + count);
            if (++count == k) {
                t = r.val;
                return;
            }

            bfs(r.left, k);
        }
    }
}